package greedy;

import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * 1005. K 次取反后最大化的数组和
 * <p>
 * 给你一个整数数组 nums 和一个整数 k ，按以下方法修改该数组：
 * <p>
 * 选择某个下标 i并将 nums[i] 替换为 -nums[i] 。
 * <p>
 * 重复这个过程恰好 k 次。可以多次选择同一个下标 i 。
 * <p>
 * 以这种方式修改数组后，返回数组可能的最大和 。
 */
public class N1005_MaxSumOfArrayAfterKNegations {
    public int largestSumAfterKNegations(int[] nums, int k) {
        // 按照绝对值从大到小排序
        nums = IntStream
                .of(nums)
                .boxed()
                .sorted(((o1, o2) -> Math.abs(o2) - Math.abs(o1)))
                .mapToInt(Integer::intValue).toArray();

        for (int i = 0; i < nums.length; i++)
            if (nums[i] < 0 && k > 0) { // k > 0 并且是负数，转为正数 k-1
                nums[i] = -nums[i];
                k--;
            }

        if (k % 2 == 1) // 如果剩下的k是单数，找到最小的那一个，转为负数
            nums[nums.length - 1] = -nums[nums.length - 1];
        return Arrays.stream(nums).sum();   //求和
    }
}
